package 算法练习;/**
 * @author： li
 * @date： 2022-01-12 15:42
 * @version 1.0
 */
/*问题描述
　　逗志芃励志要成为强力党，所以他将身上所以的技能点都洗掉了重新学技能。现在我们可以了解到，每个技能都有一个前提技能，
    只有学完了前提技能才能学习当前的技能（有一个最根本的技能不需要前提技能）。学习每个技能要消耗一个技能点，
    然后可以获得这个技能的威力值。由于逗志芃要陪妹子，所以他希望你教他如何点技能使得威力值最大从而成为强力党。
输入格式
　　第一行两个数n，m表示有n个技能和m个技能点。第二行有n个数，第i个数表示第i个技能的威力值。
　　之后的n-1行，每行两个数x,y，表示y技能的前提技能是x，也就是说先学第x个技能才能学弟y个技能。
输出格式
　　一个数，最大的威力值。
样例输入
3 2
1 10 20
1 2
1 3
样例输出
21
数据规模和约定
　　0<n,m<=200, 技能的威力值不超过200。
 */
import java.util.Scanner;

public class 强力党逗志芃_树形DP {
    static int n;//技能数
    static int m;//技能点
    static int[] wl;//存技能威力
    static int[][] a;//存技能前提
    static int[][] f;
    static int[] b;//存邻接点个数
    static int root;//存根节点
    static int[] jnd;//每个技能所消耗的技能点
    static void dfs(int u){
        for(int i=jnd[u];i<=n;i++)
            f[u][i]=wl[u];
        for(int i=0;i<b[u];i++){
            //s表示每个根节点
            int s=a[u][i];
            dfs(s);
            for(int j=m;j>=jnd[u];j--){
                for(int k=0;k<=j-jnd[u];k++){
                    f[u][j]=Math.max(f[u][j],f[u][j-k]+f[s][k]);
                }
            }
        }
    }


    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n=sc.nextInt();
        m=sc.nextInt();
        a=new int[n+1][n+1];
        wl=new int[n+1];
        f=new int[n+1][n+1];
        b=new int[n+1];
        jnd=new int[n+1];
        for(int i=1;i<=n;i++) {
            b[i]=0;
            jnd[i]=1;
        }
        for(int i=1;i<=n;i++){
            wl[i]=sc.nextInt();
        }
        for(int i=1;i<n;i++){
            sc.nextLine();
            int j=sc.nextInt();
            int k=sc.nextInt();
            a[j][b[j]++]=k;
        }
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            System.out.print(a[i][j]+" ");
        }
        System.out.println(" ");
    }
    for(int i=1;i<n;i++){
        System.out.print(b[i]+" ");
    }
        dfs(1);
    for(int i=0;i<=n;i++){
       for(int j=0;j<=n;j++){
           System.out.print(f[i][j]+" ");
       }
        System.out.println(" ");
    }
        System.out.println(f[1][m]);
    }
}
